package middle;

import java.util.Arrays;
import util.PrintUtils;

public class Solution_31 {

    public void nextPermutation(int[] nums) {
        int max = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] >= max) {
                max = Math.max(nums[i], max);
            } else {
                int index = -1;
                for (int j = nums.length - 1; j > i; j--) {
                    if (nums[j] > nums[i]) {
                        if (index == -1 || nums[index] > nums[j]) {
                            index = j;
                        }
                    }
                }
                swap(nums, i, index);
                sort(nums, i + 1, nums.length);
                return;
            }
        }
        sort(nums, 0, nums.length);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void sort(int[] nums, int begin, int end) {
        Arrays.sort(nums, begin, end);
    }

    public static void main(String[] args) {
        Solution_31 model = new Solution_31();
//        int[] nums = {2, 3, 1};
//        int[] nums = {3, 2, 1};
//        int[] nums = {1, 1, 5};
        int[] nums = {1, 3, 2};
        model.nextPermutation(nums);
        PrintUtils.arrayInt(nums);
    }
}
